package cn.edu.sjtu.stap.graph;

import java.util.*;

/**
 * This is the set to hold graph components, including edges and nodes. It also
 * provides some operations on the set. It can be treated as a collection of
 * <code>&lt;T extends GraphComponent&gt;</code>. It introduces some
 * operations on set, such as union, intersection, difference, etc.
 * 
 * @author William
 * 
 */
public class GraphComponentSet<T extends GraphComponent> implements
        IGraphComponentSet<T>, java.io.Serializable {
    private static final long serialVersionUID = 1L;

    private ArrayList<T> comps = new ArrayList<T>();

    /**
     * Default constructor. Initialize the container for the graph components.
     * 
     */
    public GraphComponentSet() {
        // Empty.
    }

    /**
     * Construct this set with a existing graph component set.
     * 
     * @param g
     *            The graph component set based on which this set will be
     *            constructed.
     */
    public GraphComponentSet(Collection<? extends T> g) {
        this(g.iterator());
    }

    /**
     * Construct this set with an graph component iterator.
     * 
     * @param i
     *            The iterator that cursors each graph component to copy into
     *            this set.
     */
    public GraphComponentSet(Iterator<? extends T> i) {
        this();
        addByIterator(i);
    }

    /**
     * Calculate the union of this set and the given set, that is to union all
     * the components in both sets, and return the result set. This operation
     * conforms to the rules of the union operation for set.
     * 
     * @param g
     *            The graph component set to union with this set.
     * @return a new graph component set for the result of the union of this set
     *         and the given set.
     */
    public GraphComponentSet<T> union(GraphComponentSet<T> g) {
        GraphComponentSet<T> r = new GraphComponentSet<T>(this);
        r.addAll(g);

        return r;
    }

    /**
     * Calculate the intersection of this set and the given set, that is to get
     * the components that exists in both sets, and return the result set. This
     * operation conforms to the rules of the intersection operation for set.
     * 
     * @param g
     *            The graph component set to intersect with this set.
     * @return a new graph component set for the result of the intersection of
     *         this set and the given set.
     */
    public GraphComponentSet<T> intersection(GraphComponentSet<T> g) {
        GraphComponentSet<T> r = new GraphComponentSet<T>(this);
        r.retainAll(g);

        return r;
    }

    /**
     * Calculate the difference of this set with the given set, that is to
     * remove all the components that are also in the given set, and return the
     * result set. This operation conforms to the rules of the difference
     * operation for set.
     * 
     * @param g
     *            The graph component set to differ from this set.
     * @return a new graph component set for the result of the difference of
     *         this set and the given set.
     */
    public GraphComponentSet<T> difference(GraphComponentSet<T> g) {
        GraphComponentSet<T> r = new GraphComponentSet<T>(this);
        r.removeAll(g);

        return r;
    }

    /**
     * Check whether this set is a subset of the given universal graph component
     * set.
     * 
     * @param g
     *            The given universal graph component set.
     * @return true if this set is a subset of the given component set,
     *         otherwise false.
     */
    public boolean isSubsetOf(GraphComponentSet<T> g) {
        if (null == g) {
            throw new NullPointerException();
        }

        return g.containsAll(this);
    }

    /**
     * Check whether this set is real subset of the given universal graph
     * component set.
     * 
     * @param g
     *            The given universal graph component set.
     * @return true if this set is a real subset of the given component set,
     *         otherwise false.
     */
    public boolean isRealSubsetOf(GraphComponentSet<T> g) {
        if (null == g) {
            throw new NullPointerException();
        }

        return g.containsAll(this) && g.size() != this.size();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object o) {
        if (!(o instanceof GraphComponentSet)) {
            return false;
        }
        GraphComponentSet g = (GraphComponentSet) o;

        if (this.size() != g.size()) {
            return false;
        }
        Iterator i = g.iterator();
        boolean b = true;

        while (b && i.hasNext()) {
            b = this.contains(i.next());
        }

        return b;
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#clone()
     */
    public Object clone() {
        return new GraphComponentSet<T>(this);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    public String toString() {
        return comps.toString();
    }

    /**
     * Add a graph component into this set, if the component is already in this
     * set, this method does nothing, otherwise add the component into this set.
     * If the given component is null, it throws an exception.
     * 
     * @param o
     *            The graph component to add into this set.
     * @return true if the given graph component is added, otherwise false.
     * @throws NullPointerException
     *             if the given graph component is null.
     */
    public boolean add(T o) {
        if (null == o) {
            throw new NullPointerException();
        }

        if (!comps.contains(o)) {
            comps.add(o);

            return true;
        }
        return false;
    }

    /**
     * Add all the graph components in the given collection into this set. Any
     * of the components that is already in this set will not be added. If this
     * set is changed, it returns true, otherwise false. If any of the
     * components in the given collection is null, it throws an exception
     * without doing anything to this set. It actually invokes
     * <code>addByIterator(Iterator&lt;? extends GraphComponent&gt;)</code> to
     * accomplish this task.
     * 
     * @param c
     *            The collection of the graph components to add.
     * @return true if this set is changed, otherwise false.
     * @throws NullPointerException
     *             if any of the component in the given set is null.
     */
    public boolean addAll(Collection<? extends T> c) {
        return addByIterator(c.iterator());
    }

    /**
     * Add all the components by traversing the given iterator. Any of the
     * components that is already in this set will not be added. If this set is
     * changed, it returns true, otherwise false. If any of the components given
     * by the iterator is null, it throws an exception without doing anything to
     * this set. It actually invokes
     * <code>addByIterator(Iterator&lt;? extends GraphComponent&gt;)</code> to
     * accomplish this task.
     * 
     * @param i
     *            The iterator which points to the graph components to add.
     * @return true if this set is changed, otherwise false.
     * @throws NullPointerException
     *             if any of the component given by the iterator is null.
     */
    public boolean addAll(Iterator<? extends T> i) {
        return addByIterator(i);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#clear()
     */
    public void clear() {
        comps.clear();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#contains(java.lang.Object)
     */
    public boolean contains(Object o) {
        return comps.contains(o);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#containsAll(java.util.Collection)
     */
    public boolean containsAll(Collection<?> c) {
        return comps.containsAll(c);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#isEmpty()
     */
    public boolean isEmpty() {
        return comps.isEmpty();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#iterator()
     */
    public Iterator<T> iterator() {
        return comps.iterator();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#remove(java.lang.Object)
     */
    public boolean remove(Object o) {
        return comps.remove(o);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#removeAll(java.util.Collection)
     */
    public boolean removeAll(Collection<?> c) {
        return comps.removeAll(c);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#retainAll(java.util.Collection)
     */
    public boolean retainAll(Collection<?> c) {
        return comps.retainAll(c);
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#size()
     */
    public int size() {
        return comps.size();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#toArray()
     */
    public Object[] toArray() {
        return comps.toArray();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Set#toArray(T[])
     */
    public <E> E[] toArray(E[] a) {
        return comps.toArray(a);
    }

    /**
     * Add all the components carried by the given iterator to this set.
     * 
     * @param i
     *            The given iterator.
     * @return true if this set is changed, otherwise false.
     */
    private boolean addByIterator(Iterator<? extends T> i) {
        boolean b = false;
        // Stores the references of the graph components to add temporarily.
        ArrayList<T> toadd = new ArrayList<T>();

        while (i.hasNext()) {
            T comp = i.next();

            if (null == comp) {
                throw new NullPointerException();
            } else if (!comps.contains(comp)) {
                toadd.add(comp);
                b = true;
            }
        }
        comps.addAll(toadd);

        return b;
    }
}
